//
// Created by wenxin on 7/17/20.
//

#ifndef TREEPOINT_GRAPH_H
#define TREEPOINT_GRAPH_H
#pragma once
#include<iostream>
#include"queue.h"
#include <pcl/point_cloud.h>
//边表节点结构，一个adjvex用来存储邻接点的位置，一个next指针用来指向下一个节点
bool DFSvisited[5000];  //用于深搜的标记数组
bool BFSvisited[5000];  //用于广搜的标记数组
typedef struct EdgeNode
{
    int adjvex;
    struct EdgeNode * next;
} EdgeNode;

//顶点表节点结构，一个data用来存储数据，一个firstedge是用来指向边表的第一个节点
typedef struct
{
    pcl::PointXYZ data;
    EdgeNode * firstedge;
} AdjList;
typedef struct
{
    AdjList adjList[5000];
    int numVertex,numEdge;
} GraphAdjList;
//这个函数是这样的，它会遍历图的顶点，然后返回一个位置（其实也就是它所在的下标）
int local(GraphAdjList G,pcl::PointXYZ val)
{
    for(int i=0; i<G.numVertex; i++)
    {
        if(G.adjList[i].data.x == val.x && G.adjList[i].data.y == val.y && G.adjList[i].data.z == val.z)
            return i;
    }
    return -1;
}
void CreateGraphAdjList(GraphAdjList &G,int numVertex,pcl::PointCloud<pcl::PointXYZ> Cloud){
    for(int i=0; i<numVertex; i++)
    {
        cout<<"第"<<i+1<<"个顶点："<<endl;
        G.adjList[i].data=Cloud.points[i];
        G.adjList[i].firstedge=NULL;
    }

}
void CreateGraphEdge(GraphAdjList & G,int numVertex, int numEdge,pcl::PointCloud<pcl::PointXYZ> Cloud,std::vector<int>pointIdxNKNSearch)
{
    int i,j,k;
    pcl::PointXYZ v1,v2;
    EdgeNode * e,* p,*q;
    //cin>>G.numVertex>>G.numEdge;
    G.numVertex=numVertex;
    G.numEdge=numEdge;
//    for(i=0; i<(G.numVertex); i++)
//    {
//        cout<<"第"<<i+1<<"个顶点："<<endl;
//        G.adjList[i].data=Cloud.points[i];
//        G.adjList[i].firstedge=NULL;
//    }
    for(k=1; k<(G.numEdge); k++)
    {
        cout<<"Vi,Vj上的顶点信息:"<<endl;
   //     cin>>v1>>v2;
        v1 = Cloud.points[pointIdxNKNSearch[0]];
        v2 = Cloud.points[pointIdxNKNSearch[k]];
        i=local(G,v1);
        j=local(G,v2);

        if(G.adjList[i].firstedge==NULL)
        {
            e= new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            G.adjList[i].firstedge=e;
        }
        else
        {
            p=G.adjList[i].firstedge;
            while(p->next!=NULL)
            {
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            p->next=e;
        }
        if(G.adjList[j].firstedge==NULL)
        {
            e= new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            G.adjList[j].firstedge=e;
        }
        else
        {
            p=G.adjList[j].firstedge;
            while(p->next!=NULL)
            {
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            p->next=e;
        }
    }
}

void Unique( GraphAdjList G) {
   for(int i=0;i<G.numVertex;i++){
       int n[5000];
       int times=0;
       int j=0;

       EdgeNode *epre = G.adjList[i].firstedge;
       while(epre !=NULL)
       {
           EdgeNode *font = epre;
           EdgeNode *judge =epre->next;
           while(judge !=NULL)
           {
               if(judge->adjvex == epre->adjvex){
                   font->next = judge->next;
                   delete judge;
                   judge = font->next;
               }
               else{
                   font = font->next;
                   judge = judge->next;
               }
           }
           epre = epre->next;
       }
   }


}

void Print(GraphAdjList G)
{
    cout<<"所建立的邻接表如以下所示："<<endl;
    for(int i=0; i<G.numVertex; i++)
    {
        cout<<G.adjList[i].data;             //先输出顶点信息
        EdgeNode * e = G.adjList[i].firstedge;
        while(e)                              //然后就开始遍历输出每个边表所存储的邻接点的下标
        {
            cout<<"-->"<<e->adjvex;
            e=e->next;
        }
        cout<<endl;
    }
}
//void BFSTraverse(GraphAdjList  G)
//{
//    EdgeNode * p;
//    queue<int>q;
//    for(int i=0; i<G.numVertex; i++)
//        BFSvisited[i]=false;
//    for(int i=0; i<G.numVertex; i++)
//    {
//        if(!BFSvisited[i])
//        {
//            BFSvisited[i]=true;
//            cout<<G.adjList[i].data<<"  ";
//            q.push(i);
//            while(!q.empty())
//            {
//                int count =q.front();
//                q.pop();
//                p=G.adjList[count].firstedge;
//                while(p)
//                {
//                    if(!BFSvisited[p->adjvex])
//                    {
//                        BFSvisited[p->adjvex]=true;
//                        cout<<G.adjList[p->adjvex].data<<"  ";
//                        q.push(p->adjvex);
//                    }
//                    p=p->next;
//                }
//            }
//        }
//    }
//}
void DestoryGraph(GraphAdjList & G)
{
    EdgeNode * p = NULL;
    for(int i=0; i<G.numVertex; i++)
    {
        p=G.adjList[i].firstedge;
        while(p)
        {
            EdgeNode * temp = p;
            p=p->next;
            delete temp;
        }
        G.adjList[i].firstedge=NULL;
    }
}
//比如v2的位置是在2 这个可以看上面的顶点表图
#endif //TREEPOINT_GRAPH_H
